for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
dp = [[0, 0, 0] for _ in range(n+1)]
for i in range(n):
dp[i+1][0] = max(dp[i+1][0], dp[i][0] + (0 if i & 1 else a[i]))
if i+2 <= n:
dp[i+2][1] = max(dp[i+2][1], max(dp[i][0], dp[i][1]) + (a[i] if i&1 else a[i+1]))
dp[i+1][2] = max(dp[i+1][2], max(dp[i][0], dp[i][1], dp[i][2]) + (0 if i&1 else a[i]))
print(max(dp[n][0], dp[n][1], dp[n][2]))
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define nl cout<<'\n'
#define ll long long
#define isodd(x) if(x&1)
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll max_subarray_sum(vector<ll> &v)
{
ll max_so_far=LLONG_MIN,max_ending_here=0;
for(auto &va:v)
{
max_ending_here+=va;
if(max_ending_here>max_so_far)
max_so_far=max_ending_here;
if(max_ending_here<0)
max_ending_here=0;
}
return max_so_far;
}
int main()
{
fast
int t,n;
cin>>t;
while(t--)
{
cin>>n;
ll a[n],ans=0,sum=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(i%2==0) sum+=a[i];
}
vector<ll> v;
for(int i=0;i<n-1;i+=2)
v.push_back(a[i+1]-a[i]);
ans=max(sum,sum+max_subarray_sum(v));
v.clear();
for(int i=1;i<n-1;i+=2)
v.push_back(a[i]-a[i+1]);
ans=max(ans,sum+max_subarray_sum(v));
cout<<ans<<endl;
}
}287B - Pipeline | 510A - Fox And Snake |
1520B - Ordinary Numbers | 1624A - Plus One on the Subset |
350A - TL | 1487A - Arena |
1520D - Same Differences | 376A - Lever |
1305A - Kuroni and the Gifts | 1609A - Divide and Multiply |
149B - Martian Clock | 205A - Little Elephant and Rozdil |
1609B - William the Vigilant | 978B - File Name |
1426B - Symmetric Matrix | 732B - Cormen --- The Best Friend Of a Man |
1369A - FashionabLee | 1474B - Different Divisors |
1632B - Roof Construction | 388A - Fox and Box Accumulation |
451A - Game With Sticks | 768A - Oath of the Night's Watch |
156C - Cipher | 545D - Queue |
459B - Pashmak and Flowers | 1538A - Stone Game |
1454C - Sequence Transformation | 165B - Burning Midnight Oil |
17A - Noldbach problem | 1350A - Orac and Factors |